UVa/11512 - GATTACA/gattaca.4.cpp

   1 /*
   2   Problem: G - GATTACA
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Fast. Takes 0.5 seconds on 100 hundred strings of length 1000.
   7
   8   Accepted.
   9  */
  10
  11 using namespace std;
  12 #include <algorithm>
  13 #include <iostream>
  14 #include <iterator>
  15 #include <sstream>
  16 #include <fstream>
  17 #include <cassert>
  18 #include <climits>
  19 #include <cstdlib>
  20 #include <cstring>
  21 #include <string>
  22 #include <cstdio>
  23 #include <vector>
  24 #include <cmath>
  25 #include <queue>
  26 #include <deque>
  27 #include <stack>
  28 #include <map>
  29 #include <set>
  30
  31 int main(){
  32   //freopen("gattaca.in", "r", stdin);
  33   int T;
  34   cin >> T;
  35   while (T--){
  36     string s;
  37     cin >> s;
  38     int n = s.size(), rep = 0;
  39     string ans = "";
  40
  41     vector<string> sufijos;
  42     string t = s;
  43     sufijos.push_back(t);
  44     while (t.size() > 0) t.erase(t.begin()), sufijos.push_back(t);
  45     sort(sufijos.begin(), sufijos.end());
  46     for (int k=1; k<sufijos.size(); ++k){
  47       int i;
  48       for (i=0; i<sufijos[k].size() && i < sufijos[k-1].size() && sufijos[k][i] == sufijos[k-1][i]; ++i);
  49       if (i > 0){
  50         t = sufijos[k].substr(0, i);
  51         if (t == ans) ++rep;
  52         else if (i > ans.size() || (i == ans.size() && t < ans)) ans = t, rep = 2;
  53       }
  54
  55     }
  56
  57     //for (int i=0; i<sufijos.size(); ++i) cout << sufijos[i] << endl;
  58
  59     if (ans.empty()) cout << "No repetitions found!\n";
  60     else cout << ans << " " << rep << endl;
  61   }
  62   return 0;
  63 }